Másele #0840

Abduqodirda \(n\) soni bor va bu sonda ‘0’ umuman qatnashmagan. Bu son ustida u quyidagi amalni istalgancha amalga oshirishi mumkin:

• Uzunligi \(l\) bo’lgan prefiks olishi (yoki chapdagi birinchi \(l\) ta sonni olishi) va uni teskarisiga aylantirishi mumkin. Shunday qilib, eng chapdagi son \(l\) – o’rinda turgan son bilan o’rin almashadi, ikki son esa \(l-1\) – o’rinda turgan son bilan. Agar son \(n = 123456789\) va \(l=5\) bo’lsa unda sonning yangi qiymati \(543216789\) ga teng bo’ladi.

\(l\) ning qiymati har bir operatsiya uchun turlicha bo’lishi mumkin va hatto u n ga teng bo’lishi ham mumkin.

Abduqodir juft sonlarni yaxshi ko’radi. Shu sababdan ham u \(n\) sonini yuqoridagi operatsiyalarni bajargan holda juft qilmoqchi, Ammo u bu ishni iloji boricha kamroq urinishlar bilan bajarmoqchi.

Abduqodirga \(n\) sonini eng kamida nechta urinishda juft qilish mumkinligini topishda yordam bering yoki bunday qilishning iloji yo’qligini ayting.

Siz \(t\) ta so’rovga javob berishingiz kerak. 

Birinchi qatorda sizga \(t\) soni beriladi. \((1 ≤ t ≤ 100000)\)

Keyingi \(t\) ta qatorning har birida sizga bitta son – n soni beriladi \((1 ≤ n < 10^9)\)

\(T\) ta qatorning har birida shu qatorga mos keladigan so’rovning qiymatini – shu sonni juft qilish uchun kerak bo’ladigan minimal urinishlar sonini chiqaring, agar buning iloji bo’lmasa \(-1\) chiqaring.